/**
 * 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
 * 输入必须是长度为 32 的 二进制串 。
 */


/**
 * 方法1：循环检查二进制位
 * 当检查第 i位时，我们可以让 n 与 2^i 进行与运算，当且仅当 n 的第 i 位为 1 时，运算结果不为 0。
 */
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        
        // 把1左移32次，循环检查n的所有位
        for(int i=0; i<32; i++){
            if(n & (1<<i)){
                count += 1;
            }
        }
        return count;

    }
};


/**
 * 方法2：位运算优化
 * n & (n−1)，其运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果。
 * 在实际代码中，我们不断让当前的 nn 与 n - 1n−1 做与运算，直到 nn 变为 00 即可。因为每次运算会使得 nn 的最低位的 11 被翻转，因此运算次数就等于 nn 的二进制位中 11 的个数。
 */

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while (n) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
};
